package 二分搜索法;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

public class No87扰乱字符串 {

    /**
     * 使用下面描述的算法可以扰乱字符串 s 得到字符串 t ：
     * 如果字符串的长度为 1 ，算法停止
     * 如果字符串的长度 > 1 ，执行下述步骤：
     * 在一个随机下标处将字符串分割成两个非空的子字符串。即，如果已知字符串 s ，
     * 则可以将其分成两个子字符串 x 和 y ，且满足 s = x + y 。
     * 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。
     * 即，在执行这一步骤之后，s 可能是 s = x + y 或者 s = y + x 。
     * 在 x 和 y 这两个子字符串上继续从步骤 1 开始递归执行此算法。
     * 给你两个 长度相等 的字符串 s1 和 s2，判断 s2 是否是 s1 的扰乱字符串。
     * 如果是，返回 true ；否则，返回 false 。
     *
     * 示例 1：
     * 输入：s1 = "great", s2 = "rgeat"
     * 输出：true
     * 解释：s1 上可能发生的一种情形是：
     * "great" --> "gr/eat" // 在一个随机下标处分割得到两个子字符串
     * "gr/eat" --> "gr/eat" // 随机决定：「保持这两个子字符串的顺序不变」
     * "gr/eat" --> "g/r / e/at" // 在子字符串上递归执行此算法。两个子字符串分别在随机下标处进行一轮分割
     * "g/r / e/at" --> "r/g / e/at" // 随机决定：第一组「交换两个子字符串」，第二组「保持这两个子字符串的顺序不变」
     * "r/g / e/at" --> "r/g / e/ a/t" // 继续递归执行此算法，将 "at" 分割得到 "a/t"
     * "r/g / e/ a/t" --> "r/g / e/ a/t" // 随机决定：「保持这两个子字符串的顺序不变」
     * 算法终止，结果字符串和 s2 相同，都是 "rgeat"
     * 这是一种能够扰乱 s1 得到 s2 的情形，可以认为 s2 是 s1 的扰乱字符串，返回 true
     * 示例 2：
     * 输入：s1 = "abcde", s2 = "caebd"
     * 输出：false
     * 示例 3：
     * 输入：s1 = "a", s2 = "a"
     * 输出：true
     *  
     * 提示：
     * s1.length == s2.length
     * 1 <= s1.length <= 30
     * s1 和 s2 由小写英文字母组成
     */

    /**
     * 正常解法过于难理解;可以换一种思路。
     * 既然两个字符串的字符对应字符完全相同,那么就可以按照统计两串的对应字符数量来验证,
     * 又因为连续切割交换,所以两串的限定区间必须要完全相同(注意反顺序),然后一直递归下去即可。
     */

    private Map<String,Boolean> map=new HashMap<>();

    public boolean isScramble(String s1, String s2) {

        Boolean aBoolean = map.get(s1 + "," + s2);
        if(aBoolean!=null&&!aBoolean){
            return false;
        }
        if(aBoolean!=null&&aBoolean){
            return true;
        }

        if(s1.length()!=s2.length()){
            return false;
        }

        if(s1.equals(s2)){
            return true;
        }

        int[] letter=new int[26];

        for (int i = 0; i < s1.length(); i++) {
            letter[s1.charAt(i)-'a']++;
            letter[s2.charAt(i)-'a']--;
        }

        for (int i = 0; i < letter.length; i++) {
            if(letter[i]!=0){
                return false;
            }
        }

        for (int i = 1; i < s1.length(); i++) {

            //正常顺序契合
            if(isScramble(s1.substring(0,i),s2.substring(0,i))&&isScramble(s1.substring(i),s2.substring(i))){
                map.put(s1+","+s2,true);
               return true;
            }
            //反顺序契合
            if(isScramble(s1.substring(0,i),s2.substring(s1.length()-i))&&isScramble(s1.substring(i),s2.substring(0,s1.length()-i))){
                map.put(s1+","+s2,true);
                return true;
            }

        }

        map.put(s1+","+s2,false);

        return false;
    }

    public static void main(String[] args) {
        No87扰乱字符串 n=new No87扰乱字符串();
        boolean result = n.isScramble("eebaacbcbcadaaedceaaacadccd", "eadcaacabaddaceacbceaabeccd");
        System.out.println(result);
    }

}
